package com.cjm.algorithm.leetcode;

/**
 * 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，
 * 并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
 *
 * 在执行上述操作后，返回包含相同字母的最长子字符串的长度。
 *
 * 示例 1：
 *
 * 输入：s = "ABAB", k = 2
 * 输出：4
 * 解释：用两个'A'替换为两个'B',反之亦然。
 * 示例 2：
 *
 * 输入：s = "AABABBA", k = 1
 * 输出：4
 * 解释：
 * 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
 * 子串 "BBBB" 有最长重复字母, 答案为 4。
 * 可能存在其他的方法来得到同样的结果。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 105
 * s 仅由大写英文字母组成
 * 0 <= k <= s.length
 */
public class Ti424 {
    public static void main(String[] args) {

    }

    public int characterReplacement1(String s, int k) {
        char[] charArray = s.toCharArray();
        int[] cur = new int[26];
        int ans = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            char c = charArray[right];
            int location = c - 'A';
            cur[location]++;
            while (!check1(cur, k)) {
                char c1 = charArray[left];
                int i = cur[c1] - 'A';
                cur[i]--;
                left ++;
            }
            ans = Math.max(ans, right - left);
        }
        return ans;
    }

    private boolean check1(int[] cur, int k) {
        int max = 0, sum = 0;
        for (int i = 0; i < 26; i++) {
            max = Math.max(max, cur[i]);
            sum += cur[i];
        }
        return sum - max <= k;
    }

    /**
     * 解：
     * 令l为符合条件的子串的左端点， r为符合条件的子串的右端点。
     * 使用cnt统计[l,r]范围的子串中每个字符串出现的次数。
     * 对于合法的子串而言， 必然有
     * sum(所有字符出现的次数) - max(出现次数最多的字符的出现的次数) =
     * other(其他字符的出现次数) <= k
     * 当找到这样的性质之后， 我们可以对s进行遍历， 每次让r右移并计数， 如果符合
     * 条件， 更新最大值；如果不符合条件，让l右移， 更新计数，直到符合条件。
     *
     * @param s
     * @param k
     * @return
     */
    public int characterReplacement(String s, int k) {
        // 转换成数组
        char[] charArray = s.toCharArray();
        // 这里是一个值得学习的点, 每个元素存在几次？
        int[] cnt = new int[26];
        int ans = 0;
        for(int l = 0,r = 0;r<s.length();r++) {
            // 这里有两个指针， 一个左指针， 一个右指针， 所以为滑动窗口
            // 一个元素是一个具体的数字, 这里是算法计算可以利用的一个点
            int cur = charArray[r] - 'A';
            // 当遍历到一个字符时， 某个元素的个数+1
            cnt[cur]++;
            // 这里， 这个算法， 最那啥的点
            // 如果符合， 那么就是， 除了最多元素外的， 其它的元素的数量 <=k， 这样就满足了题意， 而不需要
            // 减少元素了
            // 如果不满足， 那么还需要继续减少元素的数量
            while (!check(cnt, k)) {
                // 也就是说， 非元素最多的字符的数量是大于K的， 那么就得继续减少数量
                // 如果不符合的话， 这里还要进行减, 拿到最左边的元素
                int del = charArray[l] - 'A';
                // 某个元素的总数减1
                cnt[del]--;
                // 左指针继续移动
                l++;
            }
            // 此时， 去记录一下， 最多的情况
            ans = Math.max(ans, r - l + 1);
        }
        // 返回值
        return ans;
    }

    // 这个方法才是最有意思的
    private boolean check(int[] cnt, int k) {
        int max = 0, sum = 0;
        for(int i = 0;i < 26;i++) {
            // 那个元素的数量最多？
            max = Math.max(max, cnt[i]);
            // 总量+1
            sum += cnt[i];
        }
        // 元素总量 - 元素最多的元素数量
        return sum - max <= k;
    }
}
